#ifndef QUEUE_H
#define QUEUE_H

#include <stdio.h>
#include <stdlib.h>

#define MAX_NUM 100
#define FLAG 0
#define MAXVEX 100

typedef enum bool Bool;
enum bool {
	false, true
};
Bool visited[MAX_NUM];

// 顶点类型和边上的权值.
typedef int VertexType;
typedef int EdgeType;

// 边表结点.
typedef struct EdgeNode EdgeNode;
struct EdgeNode {
	int adjvex;
	EdgeType weight;
	struct EdgeNode *next;
};

// 顶点表结点.
typedef struct VertexNode *VertexNode;
typedef struct VertexNode AdjList;
struct VertexNode {
	VertexType val;
	EdgeNode *firstedge;
};

typedef int DataType_s_q;

// 图.
typedef struct graphadjlist GraphAdjList;
struct graphadjlist{
	AdjList adjList[MAXVEX];
	int numVertexes, numEdges;
};


struct Node {
        DataType_s_q val;
        struct Node *next;
};
typedef struct Node *PNode;
typedef struct Node *LinkList;

struct QNode {
	PNode front, rear;
	int len;
	int MaxSize;
};
typedef struct QNode *LinkQueue;

LinkQueue createEmptyQueue_link(void);
Bool isEmptyQueue_link(LinkQueue Q);
DataType_s_q frontQueue_link(LinkQueue Q);
void enQueue_link(LinkQueue Q, DataType_s_q x);
void deQueue_link(LinkQueue Q);
LinkQueue createLinkQueue_H(void);
void print_queue(LinkQueue Q);
void destroy_queue(LinkQueue Q);


LinkQueue createEmptyQueue_link(void)
{
	LinkQueue Q = (LinkQueue)malloc(sizeof(struct QNode));
	if (!Q) {
		printf("Out of memory! Can't malloc a queue!\n");
	}
	Q->MaxSize = MAX_NUM;
	Q->len = 0;
	Q->front = NULL;
	Q->rear = NULL;
	return Q;
}

Bool isEmptyQueue_link(LinkQueue Q)
{
	return Q->front == NULL;
}

DataType_s_q frontQueue_link(LinkQueue Q)
{
	if (isEmptyQueue_link(Q)) return FLAG;
	return Q->front->val;
}

void enQueue_link(LinkQueue Q, DataType_s_q x)
{
	if (Q->MaxSize <= Q->len) {
		printf("The queue is full now, Can't enqueue!\n");
		return ;
	}
	PNode p = (PNode)malloc(sizeof(struct Node));
	if (!p) {
		printf("Out of memory! Can't malloc a PNode to enqueue!\n");
	}
	p->val = x;
	if (Q->rear == NULL && Q->front == NULL) {
		p->next = NULL;
		Q->front = p;
	} else {
		p->next = Q->rear->next;
		Q->rear->next = p;
	}
	Q->rear = p;
	Q->len++;
}

void deQueue_link(LinkQueue Q)
{
	if (Q->len <= 0) {
		printf("The queue is empty now!Can't dequeue!\n");
		return ;
	}
	PNode tmp = Q->front;
	if (Q->rear == Q->front) {
		Q->front = Q->rear = NULL;
	} else {
		Q->front = Q->front->next;
	}
	free(tmp);
	Q->len--;
}

void destroy_queue(LinkQueue Q)
{
	if (isEmptyQueue_link(Q)) return ;
	PNode p, q;
	PNode tmp;
	p = Q->front;
	q = Q->front;
	while (q != NULL && q->next != NULL) {
		tmp = p;
		p = p->next;
		q = q->next->next;
		free(tmp);
	}
	free(Q);
}

void print_queue(LinkQueue Q)
{
	PNode p;
	for (p = Q->front; p != NULL; p = p->next)
	{
		printf("%p ", p->val);
	}
	printf("\n");
}
#endif

